public class Sort {

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length ; i++) {
            int tmp = array[i];
            int j = i -1;
            for (  ; j >= 0 ; j--) {
               if(array[j] > tmp) {
                   array[j+1] = array[j];
               } else {
                   //array[j+1] = tmp;
                   break;
               }
            }
            array[j+1] = tmp;

        }
    }

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length ; i++) {
            int minIndex = i;
            int j = i+1;


            for (; j < array.length; j++) {
                if(array[minIndex] < array[j]) {
                    minIndex = j;
                }
            }
            //swap
            swap(array,minIndex,i);

        }
    }
    private static void swap(int[] arrray,int i, int j) {
        int tmp = arrray[i];
        arrray[i] = arrray[j];
        arrray[j] = tmp;

    }
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length -1;
        while(left < right) {
            int i = left+1;
            int minIndex  = left;
            int maxIndex  = left;
            for (; i < array.length ; i++) {
                if(array[left] < array[i]) {
                    maxIndex = i;
                }
                if(array[left] > array[i]) {
                    minIndex = i;
                }
            }
            swap(array,minIndex,left);
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }
}
